import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GraphSearch {

	/**
	 * Searches the Graph passed in as an AdjcencyList(adjList) to find if a path exists from the start node to the goal node
	 * using General Graph Search.
	 * 
	 * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
	 * 
	 * The structure(struct) passed in is an empty structure may behave as a Stack or Queue and the
	 * correspondingly search function should execute DFS(Stack) or BFS(Queue) on the graph.
	 * 
	 * @param start
	 * @param struct
	 * @param adjList
	 * @param goal
	 * @return true if path exists false otherwise
	 */
	public static <T> boolean search(T start, Structure<T> struct, Map<T, List<T>> adjList, T goal) {

		struct.add(start);
		Set<T> visited = new HashSet<T>();

		while (!struct.isEmpty()){
			T u = struct.remove();
			if (u.equals(goal)) return true;
			if (!visited.contains(u)) {
				visited.add(u);
				List<T> adj = adjList.get(u);
				if (adj!=null)
					for (int i=0;i<adj.size();i++)
						if (!visited.contains(adj.get(i)))
							struct.add(adj.get(i));
			}
		}
		return false; }

	/**
	 * Find the shortest distance between the start node and the goal node in the given a weighted graph 
	 * in the form of an adjacency list where the edges only have positive weights
	 * Return the aforementioned shortest distance if there exists a path between the start and goal,-1
	 * otherwise.
	 * 
	 * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
	 * There are no negative edge weights in the graph.
	 * 
	 * @param start
	 * @param adjList
	 * @param goal
	 * @return the shortest distance between the start and the goal node
	 */
	public static <T> int dsp(T start, Map<T, List<Pair<T, Integer>>> adjList, T goal) {
		if (start==goal) return 0;
		Structure<T> queue = new StructureStack<T>();
		queue.add(start);
		Set<T> visited = new HashSet<T>();
		//for (int i=0; i<adjList.get(start).size(); i++)
		//	struct.add(adjList.get(start).get(i).a);

		Hashtable<T,Integer> distance = new Hashtable<T, Integer>();
		distance.put(start, 0);

		while (!queue.isEmpty()){
			T u = queue.remove();
			if (!visited.contains(u)) {
				visited.add(u);
				List<Pair<T, Integer>> adj = adjList.get(u);
				if (adj!=null)
					for (int i=0;i<adj.size();i++){
						queue.add(adj.get(i).a);
						if (distance.containsKey(adj.get(i).a)){
							if (distance.get(adj.get(i).a)>distance.get(u)+adj.get(i).b) {
								//distance.remove(adj.get(i).a);
								distance.put(adj.get(i).a,distance.get(u)+adj.get(i).b); }
						}
						else
							distance.put(adj.get(i).a,distance.get(u)+adj.get(i).b);
					}
			}
		}

		if (distance.containsKey(goal))
			return distance.get(goal);
		else return -1;}

}
